package Interview;

import java.util.HashMap;

public class LRUCache {
    static class Node{
        int key;
        int value;
        Node prev, next;

        Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    private final int capacity;
    private final Node dummy = new Node(0, 0);
    private HashMap<Integer, Node> nodeMap = new HashMap<>();

    public LRUCache(int capacity){
        this.capacity = capacity;
        dummy.prev = dummy;
        dummy.next = dummy;
    }

    public int get(int key) {
        Node node = getNode(key);
        return node == null? -1 : node.value;
    }

    public void put(int key, int value) {
        Node node = getNode(key);
        if(node != null){
            node.value = value;
            return;
        }
        node = new Node(key, value);
        nodeMap.put(key, node);
        if(nodeMap.size() > capacity){
            Node backNode = dummy.prev;
            nodeMap.remove(backNode);
            remove(backNode);
        }

    }

    public Node getNode(int key){
        if(!nodeMap.containsKey(key)) return null;
        Node node = nodeMap.get(key);
        // 由于操作了节点，需要移动，使其成为最新被操作过的节点
        // 方式就是先删除，再放到dummy的后面
        remove(node);
        pushFront(node);
        return node;
    }

    public void remove(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public void pushFront(Node node){
        node.next = dummy.next;
        node.prev = dummy;
        dummy.next = node;
        node.next.prev = node;
    }
}
